//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
//
// Related Topics 栈 数组 单调栈 👍 2639 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        System.out.println(solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 如果采用暴力破解的话 遍历当天节点，往前遍历，然后计算 各种组合的值 但是这种时间复杂度肯定很高 怎么优化掉呢？
         *
         * 根据宫水三叶的解法
         * 可以用两个数组left[i] 表示当前i处高度向左能扩散到哪个坐标 right[i] 表示向右能扩散到哪里
         * 就变成了找最近一个比当前大/小的值 单调栈问题
         * @param heights
         * @return
         */
        public int largestRectangleArea(int[] heights) {
            int length = heights.length;
            //默认左边扩散收到-1处
            int[] left = new int[length];
            int[] right = new int[length];
            Deque<Integer> deque = new ArrayDeque<>();
            //默认右边扩散收到length处
            Arrays.fill(right,length);
            Arrays.fill(left,-1);
            for (int i = 0; i < heights.length; i++) {
                while (!deque.isEmpty() && heights[deque.peekLast()] > heights[i]){
                    Integer index = deque.pollLast();
                    right[index] = i;
                }
                deque.addLast(i);
            }
            deque.clear();
            for (int i = length-1; i >= 0; i--) {
                while (!deque.isEmpty() && heights[deque.peekLast()] > heights[i]){
                    Integer index = deque.pollLast();
                    left[index] = i;
                }
                deque.addLast(i);
            }
            int result = Integer.MIN_VALUE;
            for (int i = 0; i < heights.length; i++) {
                result = Math.max(result,heights[i]*(right[i] - left[i] -1));
            }
            return  result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}